import java.util.Arrays;

/**
 * @author: 子龙
 */

public class TestHeap {
    public int [] elem;
    public  int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    /**
     * 初始化
     * @param arr
     */
    public void initElem(int [] arr){
        for(int i=0;i<arr.length;i++){
            this.elem[i] = arr[i];
            this.usedSize++;
        }
    }

    /**
     * 创建大根堆
     */
    public void createHeap(){
        for (int parent=(this.usedSize-1-1)/2;parent>=0;parent--){
            siftDown(parent,this.usedSize);
        }
    }

    /**
     * 向下调整建堆
     * @param parent 起始位置
     * @param usedSize 调整结束
     */
    private void siftDown(int parent, int usedSize) {
        int child  = parent*2+1;
        while(child<usedSize){
            //找到左右的最大值
            if( child+1<usedSize && elem[child]<elem[child+1]){
                child++;
            }
            if(elem[child]>elem[parent]){
                int temp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = temp;

                parent=child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }


    /**
     * 放元素 扩容
     * @param val
     */
    public void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;

        siftUp(usedSize);

        usedSize++;
    }

    /**
     * 向上调整
     * @param child
     */
    private void siftUp(int child) {
        int parent = (child-1)/2;
        while(parent>=0){
            if(elem[child]>elem[parent]){
                int temp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = temp;

                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }


    private boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 删除
     * @return
     */
    public int poll(){

        int temp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = temp;

        siftDown(0,usedSize-1);
        usedSize--;
        return temp;
    }


    /**
     * 从小到大排序
     * 先创建大根堆，再排序
     */
    public void heapSort(){
        int end=usedSize-1;
        while(end>0){
            int temp = elem[0];
            elem[0] = elem[end];
            elem[end] = temp;

            siftDown(0,end);

            end--;
        }
    }

}